package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinaryTreeZigzagLevelOrderTraversal {

	/**
	 * {1,2,3,4,5,6,7}
	 *        1
	 *     2     3
	 *   4   5 6   7
	 */
	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);
		root.right.left = new TreeNode(6);
		root.right.right = new TreeNode(7);
		
		BinaryTreeZigzagLevelOrderTraversal btzlot = new BinaryTreeZigzagLevelOrderTraversal();
		List<List<Integer>> res = btzlot.zigzagLevelOrder(root);
		
		for (List<Integer> l : res) {
			for (int i : l) {
				System.out.print(i + " ");
			}
			System.out.println();
		}
	}
	
	// use 2 stacks
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
    	if (root == null) return res;
    	
    	Stack<TreeNode> cur = new Stack<TreeNode>();
    	Stack<TreeNode> next = new Stack<TreeNode>();
    	cur.add(root);
    	
    	boolean isFromLeftToRight = false;
    	
    	while (!cur.isEmpty()) {
    		int size = cur.size();
    		List<Integer> temp = new ArrayList<Integer>();
    		
    		for (int i = 0; i < size; i++) {
    			TreeNode t = cur.pop();
    			
    			temp.add(t.val);
    			
    			if (isFromLeftToRight) {
    				if (t.right != null) next.push(t.right);
    				if (t.left != null) next.push(t.left);
    			} else {
    				if (t.left != null) next.push(t.left);
    				if (t.right != null) next.push(t.right);
    			}
    			
    		}
    		cur = next;
    		next = new Stack<TreeNode>(); 
    		res.add(temp);
    		isFromLeftToRight = !isFromLeftToRight;
    	}
    	
    	return res;
	}

}
